package code1_100.code10_20;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 */
public class _19removeNthFromEnd {

    /**
     * 思考：方法一 反转链表，删除正向第n个，然后又重新反转，输出头结点即可
     * 方法二：首先遍历一遍，计算链表长度，然后再相应的位置执行删除即可
     * 方法三：将链表入栈，出栈时在相应位置执行删除即可
     * 方法四：双指针，第一个指针为头节点，第二个指针为Nth节点，当Nth节点走至结束时，第一个指针刚好走到了要删除的位置，然后执行删除操作即可。惊为天人！！！
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.6 MB     * , 在所有 Java 提交中击败了     * 13.31%     * 的用户
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        if(head.next==null&&n==1)return null;
        head = reverse(head);
        ListNode temp = head;
        for (int i = 0; i < n-2; i++) {
            head = head.next;
        }
        if(n==1){
            head = head.next;
            head = reverse(head);
        }else {
            head.next = head.next.next;
            head = reverse(temp);
        }
        return head;
    }

    /**
     * 双指针
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.2 MB     * , 在所有 Java 提交中击败了     * 79.49%     * 的用户
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd4(ListNode head, int n) {
        if(head.next==null&&n==1)return null;
        ListNode temp = new ListNode(0,head);
        // Nth先走，first后走刚好到删除节点前端
        ListNode first = temp;
        ListNode Nth = head;
        //找到Nth的位置
        for (int i = 0; i < n; i++) {
            Nth = Nth.next;
        }
        // Nth走到头后，first为要删除节点的位置
        while (Nth!=null){
            Nth = Nth.next;
            first = first.next;
        }
        // 对节点执行删除
        first.next = first.next.next;
        ListNode ans = temp.next;
        return ans;
    }

    /**
     * 头插法进行反转链表
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head){
        ListNode result = null;
        ListNode temp;
        while (head!=null){
            // 获取到要头插的节点
            temp = head;
            head = head.next;
            // 进行头插法
            temp.next = result;
            result = temp;
        }
        return result;
    }

    public static void main(String[] args) {
        ListNode node;
        ListNode result = null;
        for (int i = 0; i < 5; i++) {
            node = new ListNode(i);
            node.next = result;
            result = node;
        }
        removeNthFromEnd4(result,3);
    }

}
